<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <div></div>
        <script>
            let vNode = {
                val: 5,
                left: {
                    val: 3,
                    left: {
                        val: 1,
                    },
                    right: {
                        val: 4,
                    },
                },
                right: {
                    val: 7,
                    left: {
                        val: 6,
                    },
                    right: {
                        val: 9,
                    },
                },
            };

            let qx = [];
            let zx = [];
            let hx = [];

            function fn(node) {
                // console.log(node.val); // 前序遍历
                qx.push(node.val);
                if (node.left) {
                    fn(node.left);
                }
                // console.log(node.val); // 中序遍历
                zx.push(node.val);
                if (node.right) {
                    fn(node.right);
                }
                // console.log(node.val); // 后序遍历
                hx.push(node.val);
            }
            fn(vNode);
            console.log(qx);
            console.log(zx);
            console.log(hx);

            // 前序遍历:

            var preorderTraversal = function (root, res = []) {
                if (!root) return res;
                res.push(root.val);
                preorderTraversal(root.left, res);
                preorderTraversal(root.right, res);
                return res;
            };
            console.log(preorderTraversal(vNode));

            // 中序遍历:

            var inorderTraversal = function (root, res = []) {
                if (!root) return res;
                inorderTraversal(root.left, res);
                res.push(root.val);
                inorderTraversal(root.right, res);
                return res;
            };
            console.log(inorderTraversal(vNode));

            // 后序遍历:

            var postorderTraversal = function (root, res = []) {
                if (!root) return res;
                postorderTraversal(root.left, res);
                postorderTraversal(root.right, res);
                res.push(root.val);
                return res;
            };
            console.log(postorderTraversal(vNode));

            // 作者：carlsun-2
            // 链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/dai-ma-sui-xiang-lu-chi-tou-qian-zhong-hou-xu-de-d/
            // 来源：力扣（LeetCode）
            // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

            // 给定一个二叉树，返回它的 后序 遍历。

            // 示例:

            // 输入: [1,null,2,3]
            //    1
            //     \
            //      2
            //     /
            //    3

            // 输出: [3,2,1]
            // 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

            // 来源：力扣（LeetCode）
            // 链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
            // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
            /**
             * Definition for a binary tree node.
             */
            function TreeNode(val, left, right) {
                this.val = val === undefined ? 0 : val;
                this.left = left === undefined ? null : left;
                this.right = right === undefined ? null : right;
            }
            /**
             * @param {TreeNode} root
             * @return {number[]}
             */
            var postorderTraversal = function (root) {};

            //   二叉树的遍历分为广度优先搜索（BFS）和深度优先搜索（DFS）两种。
            // 实现方式一共分为7种。
            // 1、BFS
            // 层次遍历（队列）
            // 2、DFS（递归/非递归）
            // 先序遍历、中序遍历、后序遍历（栈）

            // P.S.
            // 1、修改访问函数visit即可。
            // 2、关于此题的解法，有人提出根右左（NRL）的方式先序访问，最后再逆转结果，虽然可以解决问题，但并不是真正的后序遍历，不能解决普遍问题。
            // 3、后序遍历时栈中的所有节点恰好构成了当前节点的路径。

            /**
             * Definition for a binary tree node.
             * @param {*} val
             * @param {*} left
             * @param {*} right
             */
            // class TreeNode {
            //     constructor(val, left, right) {
            //         this.val = val === undefined ? 0 : val;
            //         this.left = left === undefined ? null : left;
            //         this.right = right === undefined ? null : right;
            //     }
            // }

            /**
             * 层次遍历
             * @param {BiTree} T
             * @param {Function} visit
             */
            function LevelOrder(T, visit = (x) => console.log(x.val)) {
                if (T !== null) {
                    const queue = [];
                    queue.push(T);
                    let p;
                    while (queue.length) {
                        p = queue.shift();
                        visit(p);
                        p.left && queue.push(p.left);
                        p.right && queue.push(p.right);
                    }
                }
            }

            /**
             * 先序遍历 递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function PreOrder(T, visit = (x) => console.log(x.val)) {
                if (T !== null) {
                    visit(T);
                    PreOrder(T.left, visit);
                    PreOrder(T.right, visit);
                }
            }

            /**
             * 中序遍历 递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function InOrder(T, visit = (x) => console.log(x.val)) {
                if (T !== null) {
                    InOrder(T.left, visit);
                    visit(T);
                    InOrder(T.right, visit);
                }
            }

            /**
             * 后序遍历 递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function PostOrder(T, visit = (x) => console.log(x.val)) {
                if (T !== null) {
                    PostOrder(T.left, visit);
                    PostOrder(T.right, visit);
                    visit(T);
                }
            }

            /**
             * 先序遍历 非递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function PreOrder2(T, visit = (x) => console.log(x.val)) {
                const stack = [];
                // T && stack.push(T);
                // let p;
                // while (stack.length) {
                //     p = stack.pop();
                //     visit(p);
                //     p.right && stack.push(p.right);
                //     p.left && stack.push(p.left);
                // }
                let p = T;
                while (stack.length || p) {
                    if (p) {
                        visit(p);
                        stack.push(p);
                        p = p.left;
                    } else {
                        p = stack.pop();
                        p = p.right;
                    }
                }
            }

            /**
             * 中序遍历 非递归
             * @param {BiTree} T
             * @param {Function} visit
             */
            function InOrder2(T, visit = (x) => console.log(x.val)) {
                const stack = [];
                let p = T;
                while (stack.length || p) {
                    if (p) {
                        stack.push(p);
                        p = p.left;
                    } else {
                        p = stack.pop();
                        visit(p); //和先序遍历就这一句不同
                        p = p.right;
                    }
                }
            }

            /**
             * 后序遍历 非递归
             * 这个遍历是最难的，关键在于出栈后右子树的处理
             * @param {BiTree} T
             * @param {Function} visit
             */
            function PostOrder2(T, visit = (x) => console.log(x.val)) {
                const stack = [];
                let p = T,
                    pre = null;
                while (stack.length || p) {
                    if (p) {
                        stack.push(p);
                        p = p.left;
                    } else {
                        p = stack.pop();
                        if (!p.right || p.right === pre) {
                            //没有右子树或刚访问过右子树
                            visit(p);
                            pre = p;
                            p = null;
                        } else {
                            //有右子树并且没有访问
                            stack.push(p);
                            stack.push(p.right); //右子树入栈
                            p = p.right.left; //转向右子树的左子树
                        }
                    }
                }
            }

            /**
             * NRL先序访问，逆转结果（非后序遍历）
             * @param {TreeNode} root
             * @return {number[]}
             */
            var postorderTraversal = function (root) {
                let ret = [],
                    stack = [],
                    p = root;
                while (p || stack.length) {
                    if (p) {
                        ret.push(p.val);
                        stack.push(p);
                        p = p.right;
                    } else {
                        p = stack.pop();
                        p = p.left;
                    }
                }
                return ret.reverse();
            };

            /**
             * 再啰嗦几句  关于JS递归写法，后序就是把root.val放在最后
             * 先序、中序以此类推
             * @param {TreeNode} root
             * @return {number[]}
             */
            var postorderTraversal = function (root) {
                return root === null ? [] : [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val];
            };

            // 作者：xi-yue-12
            // 链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-suo-you-bian-li-fang-fa-jian-ji-ming/
            // 来源：力扣（LeetCode）
            // 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
        </script>
    </body>
</html>
